﻿// demostu4.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
using namespace std;

typedef struct LinkNode
{
	int data;   //数据域
	struct LinkNode* next;   //指向下一个节点的指针域
	struct LinkNode* prev;   //指向上一个节点的指针域
}LinkList, LinkNode;         //Linklist是指向结构体LinkNode的指针类型

//初始化双向链表
bool InitLink(LinkList* &L)   //构造空的双向链表L
{
	L = new LinkNode;       //给L分配内存

	//给L分配内存失败则退出
	if (!L)                 
	{
		return false;
	}

	L->next = NULL;         //头节点next指针域置空
	L->prev = NULL;         //头节点prev指针域置空
	L->data = 0;        //头节点数据域置0
	return true;
}

//前插法差插入数据
bool InsertDataFront(LinkList* &L, LinkNode* node) 
{
	//内存分配失败或者没有新节点时则退出
	if (!L || !node)
	{
		return false;
	}

	//空链表时（只有头节点的时候）
	if (L->next == NULL)
	{
		node->next = NULL; //新节点node的next指针域置空
		node->prev = L; //新节点node的prev指针域指向头结点
		L->next = node;  //头节点的next指向新节点
	}
	else
	{
		L->next->prev = node;  //新插入节点node后面的节点指向新节点node
		node->next = L->next;  //新节点next指向第二个节点
		node->prev = L;        //新节点prev指向头节点
		L->next = node;        //头节点next指向新节点
	}
	return true;;
}

//尾插法
bool InsertDataBack(LinkList* &L, LinkNode* node)
{
	LinkList* last = L;  //定义一个临时的指针变量

	//内存分配失败或者没有新节点时则退出
	if (!L || !node)
	{
		return false;
	}

	//找到最后一个节点
	while (last->next)
	{
		last = last->next;
	}
	node->next = NULL;   //新节点next置空
	last->next = node;   //原链表最后一个节点的next指向新节点
	node->prev = last;   //新节点的prev指向原链表最后一个节点
	return true;
}

//指定位置插入数据
bool InsertData(LinkList* &L, int i,int& e)
{
	//如果链表为空则退出
	if (!L)
	{
		return false;
	}
	int j = 0;
	LinkList* p, * s;
	p = L;

	if (!p || j > i - 1)
	{
		return false;
	}

	//找到指定位置
	while (p && j < i - 1 )
	{
		p = p->next;
		j++;
	}
	s = new LinkList;
	s->data = e;
	s->next = p->next;
	p->next->prev = s;
	p->next = s;
	s->prev = p;

	return true;
}

//指定位置获取元素
bool GetElement(LinkList*& L, int i, int& e)
{
	int j;
	LinkList* p;

	if (!L || !L->next)
	{
		return false;
	}
	p = L->next;
	j = 1;
	while (j < i && p)
	{
		p = p->next;
		j++;
	}

	if (!p || j > i)
	{
		return false;
	}
	e = p->data;
	return true;
}

// 指定元素获取位置
bool FindElement(LinkList*& L, int e, int& index)
{
	LinkList* p;
	p = L->next;
	index = 1;
	//不存在链表或者只有头节点时退出
	if (!L || !L->next)
	{
		return false;
	}
	while (p && p->data != e)
	{
		p = p->next;
		index++;
	}
	if (!p)
	{
		index = 0;
		return false;
	}
	return true;
}
//双向链表遍历
void Print(LinkList* &L)
{
	LinkList* p = L;  //临时指针变量

	if (!L)
	{
		cout << "链表为空" << endl;
		return;
	}
	
	while (p->next)
	{
		cout << p->next->data<<"  ";
		p = p->next;
	}
	cout << endl;
}

//双向链表头删
void DeleteDataFront(LinkList*& L)
{
	if (L == NULL)
	{
		cout << "链表为空" << endl;
		return;
	}
	L = L->next;
	if (L != NULL)
	{
		L->prev = NULL;
	}
}

//尾删
void DeleteDataBack(LinkList*& L)
{
	if (L == NULL)
	{
		cout << "链表为空" << endl;
		return;
	}
	while (L->next)
	{
		L = L->next;
	}
	L->prev->next = NULL;
}

//删除元素
bool DeleteData(LinkList*& L, int i)
{
	LinkList* p, * q;
	int index = 0;
	p = L;
	if (!L || !L->next)
	{
		return false;
	}
	while ((p->next) && index < i - 1)
	{
		p = p->next;
		index++;
	}
	if (!p->next || (index > i - 1))
	{
		return false;
	}
	q = p->next;
	p->next = q->next;
	p->next->prev = p;
	delete q;
	return true;
}


int main()
{
	LinkList* L = NULL;
	LinkNode* s = NULL;
	int n = 0;   //前插次数
	int m = 0;   //尾插次数
	cout << "初始化链表" << endl;
	if (InitLink(L))
	{
		cout << "初始化成功" << endl;
	}

	//前插
	cout << "输入插入数据次数：";
	cin >> n;
	while (n > 0)
	{
		cout << "输入元素：" << endl;
		s = new LinkNode;
		cin >> s->data;
		InsertDataFront(L, s);
		n--;
	}
	Print(L);

	//尾插
	cout << "输入插入数据次数：";
	cin >> m;
	while (m > 0)
	{
		cout << "输入元素：" << endl;
		s = new LinkNode;
		cin >> s->data;
		InsertDataBack(L, s);
		m--;
	}
	Print(L);

	//任意位置插入元素
	for (int j = 0; j < 2; j++)
	{
		int i, x;
		cout << "请输入插入位置和元素：";
		cin >> i;
		cin >> x;
		InsertData(L, i, x);
		Print(L);
	}

	//根据位置获取元素
	int element = 0;
	GetElement(L, 2, element);
	cout << element << endl;
	//根据元素获取位置
	int index = 0;
	if ((FindElement(L, 10, index)))
	{
		cout << "查找成功" << index << endl;
	}
	else
	{
		cout << "不存在该元素"<<endl;
	}

	//删除指定位置元素
	DeleteData(L, 2);
	Print(L);
	return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
